package org.example.myleet.rosalind.itwv;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
        String dna = br.readLine().trim();
        List<String> patterns = new ArrayList<>();
        String line;
        while (null != (line = br.readLine())) {
            line = line.trim();
            if (line.length() < 1) break;
            patterns.add(line);
        }
        int n = patterns.size();
        int[][] matrix = new int[n][n];
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                if (canInterweave(dna, patterns.get(j), patterns.get(k))) {
                    matrix[j][k] = 1;
                } else {
                    matrix[j][k] = 0;
                }
            }
        }
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                if (k == n - 1) {
                    System.out.printf("%d", matrix[j][k]);
                } else {
                    System.out.printf("%d ", matrix[j][k]);
                }
            }
            System.out.println();
        }
        br.close();
    }

    private static boolean canInterweave(String dna, String p1, String p2) {
        int n = p1.length() + p2.length();
        //1-A, 2-C, 3-G, 4-T
        int[] wovenComposition = new int[4];
        for (char c : p1.toCharArray()) {
            updateComposition(c, wovenComposition, true);
        }
        for (char c : p2.toCharArray()) {
            updateComposition(c, wovenComposition, true);
        }
        //1-A, 2-C, 3-G, 4-T
        int[] windowComposition = new int[4];
        int i = 0;
        for (; i < n; ++i) {
            char c = dna.charAt(i);
            updateComposition(c, windowComposition, true);
        }
        while (i <= dna.length()) {
            boolean identicalComposition = true;
            for (int j = 0; j < 4; ++j) {
                if (wovenComposition[j] != windowComposition[j]) {
                    identicalComposition = false;
                    break;
                }
            }
            if (identicalComposition) {
                if (canWeave(dna.substring(i - n, i), 0, p1, 0, p2, 0)) {
                    return true;
                }
            }
            if (i < dna.length()) {
                char c = dna.charAt(i);
                updateComposition(c, windowComposition, true);
            }
            char prev = dna.charAt(i - n);
            updateComposition(prev, windowComposition, false);
            ++i;
        }
        return false;
    }

    private static boolean canWeave(String target, int i, String p1, int j, String p2, int k) {
        if (i >= target.length()) {
            return true;
        }
        char c = target.charAt(i);
        if (j < p1.length() && c == p1.charAt(j)) {
            if (canWeave(target, i + 1, p1, j + 1, p2, k)) {
                return true;
            }
        }
        if (k < p2.length() && c == p2.charAt(k)) {
            if (canWeave(target, i + 1, p1, j, p2, k + 1)) {
                return true;
            }
        }
        return false;
    }

    private static void updateComposition(char c, int[] composition, boolean add) {
        if (add) {
            if (c == 'A') {
                ++composition[0];
            } else if (c == 'C') {
                ++composition[1];
            } else if (c == 'G') {
                ++composition[2];
            } else if (c == 'T') {
                ++composition[3];
            }
        } else {
            if (c == 'A') {
                --composition[0];
            } else if (c == 'C') {
                --composition[1];
            } else if (c == 'G') {
                --composition[2];
            } else if (c == 'T') {
                --composition[3];
            }
        }
    }
}
